package mycollections;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyHashMap<K, V> implements MyMap<K, V> {

	int size;
	SimpleEntry<K, V>[] table;
	private int initialCapacity = 16;
	private float loadFactor = 0.75f;
	int threshold;

	public MyHashMap() {
		threshold = (int) (initialCapacity * loadFactor);
		table = new SimpleEntry[initialCapacity];
	}

	public MyHashMap(int initialCapacity) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
		this.initialCapacity = initialCapacity;
		threshold = (int) (initialCapacity * loadFactor);
		table = new SimpleEntry[initialCapacity];
	}

	public MyHashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
		if (loadFactor <= 0 || Float.isNaN(loadFactor))
			throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
		this.initialCapacity = initialCapacity;
		this.loadFactor = loadFactor;
		threshold = (int) (initialCapacity * loadFactor);
		table = new SimpleEntry[initialCapacity];
	}
	
	public Iterator<MyMap.Entry<K, V>> entryIterator() {
		return new EntryIterator<MyMap.Entry<K, V>>();
	}

	public V put(K key, V value) {
		if (key == null)
			return putNullKey(value);
		int hash = key.hashCode();
		int index = indexFor(hash, table.length);	
		for (SimpleEntry<K, V> e = table[index]; e != null; e = e.next) {
			if (e.hash == hash && (e.key == key || key.equals(e.key))) {
				V oldValue = e.value;
				e.value = value;
				return oldValue;
			}
		}
		addEntry(hash, key, value, index);
		return null;
	}

	public V get(K key) {
		if (key == null)
			return getNullKey();
		Entry<K, V> entry = getEntry(key);
		if(entry == null)
			return null;
		return entry.getValue();
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public V remove(Object key) {
		SimpleEntry<K, V> e = removeEntryForKey(key);
		if (e == null)
			return null;
		else
			return e.value;
	}

	public void clear() {
		for (int i = 0; i < table.length; i++)
			table[i] = null;
		size = 0;
	}

	Entry<K, V> getEntry(Object key) {
		int hash = key.hashCode();
		for (SimpleEntry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
			if (e.hash == hash && (e.key == key || key.equals(e.key)))
				return e;
		}
		return null;
	}

	public boolean containsKey(K key) {
		return getEntry(key) != null;
	}

	public boolean containsValue(V value) {
		if (value == null)
			return containsNullValue();
		for (int i = 0; i < table.length; i++)
			for (SimpleEntry<K, V> e = table[i]; e != null; e = e.next)
				if (value.equals(e.value))
					return true;
		return false;
	}

	private SimpleEntry<K, V> removeEntryForKey(Object key) {
		int hash;
		if (key == null)
			hash = 0;
		else
			hash = key.hashCode();
		int i = indexFor(hash, table.length);
		SimpleEntry<K, V> prev = table[i];
		SimpleEntry<K, V> e = prev;
		while (e != null) {
			SimpleEntry<K, V> next = e.next;
			if (e.hash == hash && (e.key == key || key.equals(e.key))) {
				size--;
				if (prev == e)
					table[i] = next;
				else
					prev.next = next;
				return e;
			}
			prev = e;
			e = next;
		}
		return e;
	}

	private boolean containsNullValue() {
		for (int i = 0; i < table.length; i++)
			for (SimpleEntry<K, V> e = table[i]; e != null; e = e.next)
				if (e.value == null)
					return true;
		return false;
	}

	private V getNullKey() {
		for (SimpleEntry<K, V> e = table[0]; e != null; e = e.next) {
			if (e.key == null)
				return e.value;
		}
		return null;
	}

	private void resize(int newCapacity) {
		SimpleEntry<K, V>[] newTable = new SimpleEntry[newCapacity];
		for (SimpleEntry<K, V> e : table) {
			while (e != null) {
				SimpleEntry<K, V> next = e.next;
				if (e.key == null)
					e.hash = 0;
				else
					e.hash = e.key.hashCode();
				int i = indexFor(e.hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			}
		}
		table = newTable;
		threshold = (int) (initialCapacity * loadFactor);
	}

	private int indexFor(int h, int length) {
		return h & (length - 1);
	}

	private V putNullKey(V value) {
		for (SimpleEntry<K, V> e = table[0]; e != null; e = e.next) {
			if (e.key == null) {
				V oldValue = e.value;
				e.value = value;
				return oldValue;
			}
		}
		addEntry(0, null, value, 0);
		return null;
	}

	private void addEntry(int hash, K key, V value, int bucketIndex) {		
		if ((size >= threshold) && (null != table[bucketIndex])) {
			resize(2 * table.length);
			bucketIndex = indexFor(hash, table.length);
		}
		SimpleEntry<K, V> e = table[bucketIndex];
		table[bucketIndex] = new SimpleEntry<K, V>(hash, key, value, e);
		size++;
	}

	private class EntryIterator<E> implements Iterator<MyMap.Entry<K, V>> {
		SimpleEntry<K, V> next;		
		SimpleEntry<K, V> current;
		int index;

		EntryIterator() {
			if (size > 0) { 				
				while (index < table.length && (next == null))
					next = table[index++];		
			}
		}

		public MyMap.Entry<K, V> next() {
			SimpleEntry<K, V> e = next;
			if (e == null)
				throw new NoSuchElementException();
			if ((next = e.next) == null) {
				while (index < table.length && (next == null))
					next = table[index++];
			}
			current = e;
			return e;
		}

		public void remove() {
			if (current == null)
				throw new IllegalStateException();
			Object k = current.key;
			current = null;
			MyHashMap.this.removeEntryForKey(k);
		}

		public final boolean hasNext() {
			return next != null;
		}
	}

	static class SimpleEntry<K, V> implements MyMap.Entry<K, V> {

		private V value;
		private K key;
		SimpleEntry<K, V> next;
		private int hash;

		public SimpleEntry(int hash, K key, V value, SimpleEntry<K, V> next) {
			this.hash = hash;
			this.key = key;
			this.value = value;
			this.next = next;
		}

		public K getKey() {
			return key;
		}

		public V setValue(V value) {
			V old = this.value;
			this.value = value;
			return old;
		}

		public V getValue() {
			return value;
		}

		public int hashCode() {
			return value.hashCode();
		}

		public boolean equals(Object obj) {
			return this.value.equals(obj);
		}
	}

}
